# 58/100 回溯-括号生成
# leetcode第22题: https://leetcode.cn/problems/generate-parentheses/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/4

from leetcode import test
import json


def generateParenthesis(n: int) -> list[str]:
    res = []

    def backtracking(path, start, end):
        """
        :param path: 已经选择的字符串
        :param start: start表示已选择字符串中左括号的数量
        :param end: end表示已选择字符串中右括号的数量
        :return:
        """
        if len(path) == n * 2:
            res.append(''.join(path))
            return
        if start < n:
            path.append("(")
            backtracking(path, start + 1, end)
            path.pop()
        if end < start:
            path.append(")")
            backtracking(path, start, end + 1)
            path.pop()

    backtracking([], 0, 0)
    res.sort()
    return res


def generateParenthesis_dfs(n: int) -> list[str]:
    m = n * 2
    res = []
    path = [''] * m

    def dfs(i, open):
        if i == m:
            res.append(''.join(path))
        if open < n:
            path[i] = '('
            dfs(i + 1, open + 1)
        if i - open < open:
            path[i] = ')'
            dfs(i + 1, open)

    dfs(0, 0)
    res.sort()
    return res


if __name__ == '__main__':
    with open("../data/j_backtrack5_lc22.data", "r") as file:
        lines = file.read().strip()
        jo = json.loads(lines)

    inp = [{"n": 3}, {"n": 1}, {"n": 5}, {"n": 8}]
    out = [
        ["((()))", "(()())", "(())()", "()(())", "()()()"],
        ["()"],
        ['((((()))))', '(((()())))', '(((())()))', '(((()))())', '(((())))()', '((()(())))', '((()()()))', '((()())())',
         '((()()))()', '((())(()))', '((())()())', '((())())()', '((()))(())', '((()))()()', '(()((())))', '(()(()()))',
         '(()(())())', '(()(()))()', '(()()(()))', '(()()()())', '(()()())()', '(()())(())', '(()())()()', '(())((()))',
         '(())(()())', '(())(())()', '(())()(())', '(())()()()', '()(((())))', '()((()()))', '()((())())', '()((()))()',
         '()(()(()))', '()(()()())', '()(()())()', '()(())(())', '()(())()()', '()()((()))', '()()(()())', '()()(())()',
         '()()()(())', '()()()()()'],
        jo['ans']
    ]

    test.test_function(generateParenthesis, inp, out)
    test.test_function(generateParenthesis_dfs, inp, out)
